package main

import "fmt"

/**
给定一个整数数组 `nums` 和一个正整数 `k`，
找出是否有可能把这个数组分成 `k` 个非空子集，其总和都相等

输入： nums = [4, 3, 2, 3, 5, 2, 1], k = 4
输出： True
说明： 有可能将其分成 4 个子集（5），（1,4），（2,3），（2,3）等于总和。

1 <= k <= len(nums) <= 16
0 < nums[i] < 10000
*/
func main() {
	nums := []int{4, 3, 2, 3, 5, 2, 1}
	fmt.Println(solution(nums, 4))
}

func solution(nums []int, k int) bool {
	sum, maxNum := 0, 0
	for _, num := range nums {
		sum += num // 找出集合总和
		if maxNum < num {
			// 找出最大数字
			maxNum = num
		}
	}
	//每个集合的和一定等于sum/k，所以 sum/k一定能除尽，集合中的元素的值不能超过sum/k。
	if sum%k != 0 || maxNum > sum/k {
		return false
	}
	// 用来标记使用过的数字
	used := make([]bool, len(nums))

	return backTracking(nums, k, sum/k, 0, 0, used)
}

//参数cur是当前这个集合中已有的和
func backTracking(nums []int, k int, target int, cur int, start int, used []bool) bool {
	// 返回条件，这里K==1，说明还剩下一个，
	//由于最开始进入这个函数的条件sum/k的原因，
	//剩下的那一个必然能和剩余的集合组成目标集合。
	if k == 1 {
		return true
	}
	// 满足条件了，已经找打了一个集合
	if cur == target {
		return backTracking(nums, k-1, target, 0, 0, used)
	}
	// 遍历剩下的数字
	for i := start; i < len(nums); i++ {
		// 数字没用过，且加上这个数字集合不超过目标值
		if !used[i] && cur+nums[i] <= target {
			used[i] = true
			if backTracking(nums, k, target, cur+nums[i], i+1, used) {
				return true
			}
			// 回溯，表明这个数字在当前集合中不行
			used[i] = false
		}
	}
	return false
}
